# -*- coding: utf-8 -*-
"""
    Time    : 2021/1/6 12:58 下午
    Author  : Thinkgamer
    File    : 019-删除链表的倒数第N个节点.py
    Desc    : https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
"""
"""
给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：
你能尝试使用一趟扫描实现吗？
"""
class ListNode:
	def __init__(self, val):
		self.val = val
		self.next = None


# 扫描两遍，第一遍求长度，第二遍删除数据
# 40ms 72.23% | 14.7mb 10.42%
def remove_nth_from_end_v1(head, n):
	count = 0
	temp = head
	while temp:
		temp = temp.next
		count += 1
	
	root = head
	if n == count:
		return head.next
	elif n == 1:
		while root.next.next:
			root = root.next
		root.next = None
	else:
		while root.next:
			if count == n + 1:
				root.next = root.next.next
			root = root.next
			count -= 1
	return head
	

# 快慢指针法，定义两个指针（first，second），second先走n步，然后 first 和 second 同时走，当second走到终点时，first所指的下一个 即为要删除的元素
# 44ms 46.63% | 14.8mb 7.79%
def remove_nth_from_end_v2(head, n):
	first = head
	second = head
	while n > 0:
		second = second.next
		n -= 1
	if not second:
		return head.next
	while second.next:
		second = second.next
		first = first.next
	if first.next.next:
		first.next = first.next.next
	else:
		first.next = None
	
	return head


# 基于栈的思路，遍历一个入栈一个，遍历一遍之后，知道总的长度，然后开始出栈，出到对应位元素的时候，将其删除
# 48ms 22.44% | 14.9mb 5.20%
def remove_nth_from_end_v3(head, n):
	count = 0
	stack = list()
	first = head
	while first:
		stack.append(first)
		count += 1
		first = first.next
	if count == n:
		return head.next
	else:
		while n >= 0:
			if n == 0:
				node = stack.pop()
				if node.next.next:
					node.next = node.next.next
				else:
					node.next = None
				return head
			else:
				stack.pop().val
				n -= 1


# 创建一个链表
one = ListNode(1)
two = ListNode(2)
# three = ListNode(3)
# four = ListNode(4)
# five = ListNode(5)
one.next = two
# two.next = three
# three.next = four
# four.next = five
head = remove_nth_from_end_v3(one, 1)
while head:
	print(head.val)
	head = head.next
